// https://www.lintcode.com/problem/24-game/description

class Solution {
public:
    /**
     * @param nums: 4 cards
     * @return: whether they could get the value of 24
     */
    // [1,5,5,5] (5 - 1/5) * 5
    bool helper (vector<double> nums, double target) {
        if (nums.size() == 1) {
            // return nums[0] == target;
            return fabs(nums[0] - target) <= 1e-6; //注意！！
        }
        else {
            for (int i = 0; i < nums.size(); ++i) {
                vector<double> tmp = nums;
                tmp.erase(find(tmp.begin(), tmp.end(), nums[i])); 
               
                if (helper(tmp, target - nums[i]) || helper(tmp, nums[i] - target) || helper(tmp, target + nums[i]) || helper(tmp, target * nums[i]) || helper(tmp, target / nums[i]) || helper(tmp, nums[i] / target)) {
                    return true;
                }
            }
        }
        return false;
    }
    bool compute24(vector<double> &nums) {
        return helper(nums, 24);
    }
};



class Solution {
public:
    /**
     * @param nums: 4 cards
     * @return: whether they could get the value of 24
     */
    bool helper(vector<double> &nums, int n) 
    {
        // if (nums.size() == 1) 
        if (n == 1)
        {
            return fabs(nums[0] - 24) <= 1e-6;
        }
        for (int i = 0; i < n; ++i) 
        {
            for (int j = i + 1; j < n; ++j) 
            {
                double a = nums[i];
                double b = nums[j];
                nums[i] = a + b;
                nums[j] = nums[n - 1];
                if (helper(nums, n - 1)) 
                {
                    return true;
                }
                nums[i] = a - b;
                if (helper(nums, n - 1)) 
                {
                    return true;
                }
                nums[i] = b - a;
                if (helper(nums, n - 1)) 
                {
                    return true;
                }
                nums[i] = a * b;
                if (helper(nums, n - 1)) 
                {
                    return true;
                }
                if (b != 0) //注意！
                {
                    nums[i] = a / b;
                    if (helper(nums, n - 1)) 
                    {
                        return true;
                    }
                }
                if (a != 0)
                {
                    nums[i] = b / a;
                    if (helper(nums, n - 1)) 
                    {
                        return true;
                    }
                }
                nums[i] = a;
                nums[j] = b;
            }
        }
        return false; //注意！
    }
    
    bool compute24(vector<double> &nums) {
        return helper(nums, nums.size());
    }
};